package tree.递归;

import po.TreeNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 二叉树中的最大路径和124.java
 * @Description TODO https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
 * @createTime 2021年04月09日 12:41:00
 */
public class 二叉树中的最大路径和124 {
    /**
     *
     * 1. 选出左右子树的最大的值，值需要大于0
     * 2. 计算左右节点和跟节点的值
     * 3. 比较新的值和旧的值的大小
     * 4、选择左右子树
     */
    int sum=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root==null){
            return 0;
        }
        maxPath(root);
        return sum;
    }

    private int maxPath(TreeNode root) {
        if (root==null){
            return 0;
        }
        //计算左右节点的值,在节点的值大于0的时候才行
        int leftSum=Math.max(maxPath(root.left),0);
        int rightSum=Math.max(maxPath(root.right),0);
        //计算新的路径的和
        int newSum=leftSum+rightSum+root.val;
        //选出新值和 旧值的大小
        sum = Math.max(newSum, sum);
        //返回最大值
        return root.val+Math.max(leftSum,rightSum);
    }
}
